package dynamicprogramming.两个字符串的删除操作;
/**
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
 *  每步 可以删除任意一个字符串中的一个字符。
 *  示例 1：
 * 输入: word1 = "sea", word2 = "eat"
 * 输出: 2
 * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
 *  示例 2:
 * 输入：word1 = "leetcode", word2 = "etco"
 * 输出：4
 *  提示：
 *  1 <= word1.length, word2.length <= 500
 *  word1 和 word2 只包含小写英文字母
 *  Related Topics 字符串 动态规划 👍 681 👎 0
 */
public class Solution {
    public static void main(String[] args) {
        minDistance("sea","eat");
    }

    /**
     * 解题思路：假设 i 为 word1 的第i个字符 ， j 为 word2的 第j个字符。那么要求word1 和 word2 需要调整多少次达到一致 即f(i,j)
     * 1. 当 i 和 j 字符相同时 f(i,j) = f(i-1,j-1)。
     * 2. 当 i 和 j 字符不相等 f(i,j) = min(f(i-1,j),f(i,j-1))+1。 原理： 就是将word1前i 或者 word2 前j 主动拿掉其中 i 或者 j字符 也就是 操作数 + 1  ；
     *    而这个时候就只需要知道是拿掉i还是拿掉j能得到最小值就行
     * 注意: 这里需要把""看作是最小的字符，也是要计算在内的
     * @param word1
     * @param word2
     * @return
     */
    public static int minDistance(String word1, String word2) {
        int lenW1 = word1.length();
        int lenW2 = word2.length();
        int[][] temp = new int[lenW1+1][lenW2+1];
        for (int i = 0; ; i++) {
            if (i<=lenW1){
                temp[i][0] = i;
            }
            if (i<=lenW2){
                temp[0][i] = i;
            }
            if (i>lenW1&&i>lenW2){
                break;
            }
        }
        for (int i = 1; i <=lenW1 ; i++) {
            for (int j = 1; j <= lenW2; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    temp[i][j] = temp[i - 1][j - 1];
                }else{
                    temp[i][j] = Math.min(temp[i - 1][j],temp[i][j-1])+1;
                }
            }
        }
        for (int i = 0; i <=lenW1 ; i++) {
            for (int j = 0; j <= lenW2; j++) {
                System.out.print(temp[i][j]+"   ");
            }
            System.out.println();
        }
        return 1 ;
    }
}
